package BNS.wheat;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;
import java.io.PrintStream;
import BNS.graphs.*;
import BNS.plumbing.*;

/** This class sets up orders and executes trades in a Wheat/Milk Market.
	Orders arrive one at a time. The player placing an order is called the buyer.
	If his order matches or exceeds the price of any existing price, an
	exchange is transacted. If the price does not match, or if any of his order
	does not fully clear at the time of placing the order, his order is left
	standing, and he is subsequently called a seller.
	*/
public class Market {
	
	/** utility method to format a number for printing.
		When decimal input is converted to binary form, sometimes its representation is 
		inexact; For instance, 0.2 might become 0.20000002 and 0.8 could become 0.79999995 .
		This method attempts to round off a number to what it may have been originally specified as
		during human input. It looks for a sequence of four 9's or four 0's and performs the
		roundoff that seems appropriate.
		@param x the number to be output
		@return a String containing the decimal number that approximates x.
		*/
	public static String roundOff(double x) {
		String s= String.format("%.30f",x-(int)x);
		if (s.endsWith(".")) return String.format("%f",x);
		int i= s.indexOf("9999");
		int j= s.indexOf("0000");
		if (i<0 && j<0) return ((int)x)+s;
		if (i<0) i=j;
		if (j>0 && i>j) i=j;
		String f= String.format("%%.%df",i-s.indexOf(".")-1);
		return String.format(f,x);
		}
	
	/** This is a utility structure containing the 2 fields that define a trade:
		how much is paid, and how much is obtained.
		*/
	public static class Deal implements java.io.Serializable { 
		double pay, get; 
		public Deal(double p, double g) { pay= p>0? p : 0.f; get= g>0? g : 0.f; }
		public double rate() { if (get>0) return pay/get; else return 0.f; }
		public String toString() { return String.format("(%.2f/%.2f)",pay,get); }
		public String round() { return roundOff(pay)+" "+roundOff(get); }
		public String toString(WheatMktGame.Commodity stuff) {
			return "will pay "+pay+" of "+stuff+" to get "+get;
			}
		}
	
	protected NodeState[] neighbours;	// stuff pertaining to nodes, indexed by Node.getIndex()s
	protected int[] perm;
	protected Deal[] offers, costFn;
	private int size, firstVendor;
	public final double originalVolume, originalBudget;
	private PrintStream gameLog;		// for printing game data
	
	/** Constructs an object that is optimized for executing trades in a particular
		graphlet neighbourhood.
		@param nhbrs the array of NodeStates that holds all the players in a marketplace.
		The first element [0] is the player; all others are his neighbours.
		*/
	public Market(NodeState[] nhbrs, PrintStream gLog) {
		size= nhbrs.length;		// # neighbours +1
		perm= new int[size];	// perm[0]= 0, but never used
		offers= new Deal[size];
		offers[0]= new Deal(0,0);
		costFn= new Deal[size];
		costFn[0]= new Deal(0,0);
		rebuild(nhbrs);
		originalVolume= totalVolume();
		originalBudget= endowment();
		//System.err.println("Market defined for "+size+" neighbours");
		gameLog= gLog;
		}
	
	/** returns the state of the neighbour with given index */
	public NodeState vendor(int idx) { return neighbours[perm[idx]]; }
	/** returns the number of neighbours */
	public int numVendors() { return neighbours.length-1; }
	/** returns the total amount of goods that the neighbours still possess */
	public double totalVolume() { return costFn[costFn.length-1].get; }
	/** returns the total cost of buying the current totalVoume() */
	public double totalCost() { return costFn[costFn.length-1].pay; }
	
	/** returns the current amount of goods left to be sold by the eigennode */
	public double endowment() { return neighbours[0].endowment; }
	/** returns the current total amount of goods that the eigennode has purchased */
	public double acquired() { return neighbours[0].acquired; }
	/** returns the price posted in the current sales order */
	public double myPrice() { return neighbours[0].sellingPrice; }
	/** returns the amount of goods for sale by the eigennode */
	public double myVolume() { return neighbours[0].sellingVolume; }
	
	/** rebuilds the arrays offers[], perm[] and costFn[].
		offers[] is left with seller's prices sorted into increasing order.
		("Sellers" are all the neighbours whose orders are left prior to the current one.)
		perm[i] is left holding the index of the neighbour whose price is the i'th smallest.
		costFn[i] is left holding the Deal that neighbour[perm[i]] posted.
		The costFn array is used in the buyFor(pay) and payFor(get) functions.
		*/
	public void rebuild(NodeState[] nhbrs) {
		//System.err.println("rebuild, size= "+size+", length="+nhbrs.length);
		assert(size==nhbrs.length);
		neighbours= nhbrs;
		for (int i=1; i<neighbours.length; i++) {
			NodeState ns= neighbours[i];
			int j= 1;
			while (j<i && ns.sellingPrice > neighbours[perm[j]].sellingPrice)
				j++;
			/*System.err.print(i+":"+j+" "+ns+" ---> "+ ns.sellingPrice);
			if (j<i) 
				System.err.println(" <= ["+perm[j]+"] "+neighbours[perm[j]].sellingPrice);
			else System.err.println(" > all others");*/
			for (int k=i-1; k>=j; k--) 
				perm[k+1]= perm[k]; 
			perm[j]= i;
			/*for (int k=0; k<=i; k++) System.err.print("  "+perm[k]);
			System.err.println("   <--- perm "+i);	*/
			}
		firstVendor= 1;
		double nextPay=0.f, nextGet=0.f;
		for (int i=1; i<neighbours.length; i++) {
			NodeState ns= neighbours[perm[i]];
			System.err.println(perm[i]+" selling price="+
								ns.sellingPrice+",  volume="+ ns.sellingVolume);
			offers[i]= new Deal(ns.sellingPrice * ns.sellingVolume, ns.sellingVolume);
			nextPay+= offers[i].pay;
			nextGet+= offers[i].get;
			costFn[i]= new Deal(nextPay, nextGet);
			if (offers[i].get<=0) firstVendor= i+1;
			}
		show("offers",offers);
		//show("costFn",costFn);
		}
	
	/* 	The current Deal order=(PAY,GET) specifies the amount of the buyer's good 
		to PAY and the amount of the seller's good to GET.
		If any existing trade orders exist with a price no higher than PAY/GET, then 
		a transaction occurs. A trade always uses the seller's (previously posted) price.
		As many exchanges will occur as are required to consume all the PAY
		(in order of increasing price), but no exchanges will occur at a higher price.
		In the event that not all the PAY is consumed, the remainder is left on the 
		market as a pending offer, and its selling price is listed as GET/PAY.
		@param order the PAY and GET quantities involved.
		@return the total amount of goods PAYed by the buyer. (This is the same
		as the amount hisr endowment was reduced by).
		*/
	public double trade(Deal order) {
		if (order.pay <= 0.f || order.get<= 0.f) {
			neighbours[0].sellingPrice= 0;	//	Float.MAX_VALUE?   bug?
			neighbours[0].sellingVolume= 0;
			return 0f;
			}
		// trades will be executed on the *server* (not on the client!), so we
		rebuild(neighbours);	// gotta refresh the server's version of the market.
		double was= neighbours[0].endowment;
		//System.err.println();
		
		double buyingPrice= order.rate();
		double buyingVolume= order.get;
		neighbours[0].sellingPrice= (float)(1/buyingPrice);
		if (order.pay > endowment()) {
			neighbours[0].sellingVolume= (float)endowment();
			System.err.print("Insufficient funds to buy "+buyingVolume);
			buyingVolume= endowment()/buyingPrice;
			System.err.println("; order lowered vol to "+buyingVolume);
			gameLog.println("djst "+neighbours[0].sellingVolume+" "+buyingVolume);
			}
		else 
			neighbours[0].sellingVolume= (float)order.pay;
		//System.err.println("wanna buy "+buyingVolume+" @"+buyingPrice
		//				   +", paying "+neighbours[0].sellingVolume);
		
		double rate= buyingPrice;
		int i= 1;	// i=firstVendor;
		while (i < offers.length
			&& neighbours[0].sellingVolume > 0
			&& neighbours[0].sellingVolume >= offers[i].pay
//			&& offers[i].pay > 0		// sometimes 0s occur at front of sorted list!
			&& offers[i].rate() <= rate) {
			if (offers[i].pay > 0 && offers[i].get > 0) {
				System.err.format("gobbling bar %d %s @ %.3f%n", i,offers[i],offers[i].rate());
				exchange(0,offers[i].pay, perm[i],offers[i].get);
				}
			else System.err.print("<"+i+">");
			i++;
			}
		System.err.println("finished gobbling "+i);
		if (i < offers.length
			&& neighbours[0].sellingVolume > 0
			&& offers[i].pay > 0
			&& offers[i].rate() <= rate) {
			double pay= neighbours[0].sellingVolume;
			double get= pay/offers[i].rate();
			System.err.format("nibbling bar %d (%.2f:%.2f) @ %.3f%n",
							  i, pay,get,  offers[i].rate());/**/
			exchange(0,pay, perm[i],get);
			tieTest(i,true);
			}
		else { if (was > neighbours[0].endowment) tieTest(i-1,false); }
		double totalPay= was - neighbours[0].endowment;
		//System.err.println("total transferred= "+ totalPay);
		assert(neighbours[0].sellingVolume>=0);
//		if (offers[2].pay==0 && offers[3].pay>0) System.exit(0);
		return totalPay;
		}
	
	/** detects occasions where arbitrary breaking of price ties may have affected outcomes. */
	private void tieTest(int i, boolean loseToo) {
		if (neighbours[0].sellingVolume > 0) return;	// buyer still hungry => no seller willing
//		PrintStream gameLog= System.err;
		double rate= offers[i].rate();
		boolean winner=false, loser=false;
		Vector<Integer> ties= new Vector<Integer>();
//		ties.add(i); if (loseToo) ties.add(-i);
//		System.err.format("testing ");
		for (int k=1; k<offers.length; k++) {
//			System.err.format(" %d",k);
			if (offers[k].rate()==rate && offers[k].pay>0) {
//				System.err.format("?");
//				if (k<i) { ties.add(+k); winner= true; }//System.err.format("W");}
//				if (i<k) { ties.add(-k); loser=  true; }//System.err.format("L");}
				ties.add(k);
				winner= winner || (k<i);
				loser = loser  || (i<k);
				}
			}
//		System.err.println();
		if (winner && loseToo || loser) {
			System.err.format(" %d neighbours tied with %d %b %b %b%n", 
								ties.size(),i, loseToo,winner,loser);
			if (gameLog!=null) {
//				gameLog.format("tied %s %s    ", offers[i], roundOff(rate));
				gameLog.format("ties %s    ", rate);
				for (Enumeration e = ties.elements() ; e.hasMoreElements() ;) {
					int index= ((Integer)e.nextElement()).intValue();
					int permi= perm[Math.abs(index)];
					int nodeNum= neighbours[permi].index+1;
//					gameLog.print((index>0?" +":" -") +nodeNum);
					gameLog.print("   "+nodeNum+" "+neighbours[permi].sellingVolume);
					}
				gameLog.println();
				}
			}
/*		int first= i; while (first>1 && offers[first-1].rate()==rate) first--;
		int larst= i; while (larst+1<offers.length && offers[larst+1].rate()==rate) larst++;
		if (first<larst) {
			System.err.format("neighbours tied %d (%d) %d %b%n",	first,i,larst,loseToo);
			if (gameLog!=null) {
				gameLog.format("tied %s %s    ", offers[i], roundOff(rate));
				for (int ii=first; ii<=i; ii++) gameLog.format(" +%d",neighbours[perm[ii]].index+1);
				int L= loseToo? i : i+1;
				for (int ii=L; ii<=larst; ii++) gameLog.format(" -%d",neighbours[perm[ii]].index+1);
				gameLog.format("%n");
				}
			if (rate==0) {
				for (int ii=0; ii<offers.length; ii++) 
					System.err.format("%10.3f %10.3f %10.3f   %4d%n",
						offers[ii].pay, offers[ii].get, offers[ii].rate(), perm[ii]);
				System.exit(0);
				}
			} */
		}
	
	/** performs a few sanity checks and then exchanges 
		a given amount (vol1) of goods belonging to neighbour # idx1 for 
		a given amount (vol2) of goods belonging to neighbour # idx2.
		*/
	private void exchange(int idx1, double vol1, int idx2, double vol2) {
		//System.err.format("exchange: %d gives %.2f,  %d gives %.2f%n", idx1,vol1,  idx2,vol2);
		if (gameLog!=null)
			gameLog.format("exch %d %s\t %d %s%n",	neighbours[idx1].index+1,vol1,  
													neighbours[idx2].index+1,vol2);
		/*
		System.err.format("%d endow %f selling %f at %f%n", idx1, neighbours[idx1].endowment, 
						  neighbours[idx1].sellingVolume, neighbours[idx1].sellingPrice);
		System.err.format("%d endow %f selling %f at %f%n", idx2, neighbours[idx2].endowment, 
						  neighbours[idx2].sellingVolume, neighbours[idx2].sellingPrice);
		//System.err.println("diff "+ (neighbours[idx1].sellingVolume - vol1));
		*/
		assert(neighbours[idx1].endowment >= neighbours[idx1].sellingVolume);
		assert(neighbours[idx2].endowment >= neighbours[idx2].sellingVolume);
		assert(neighbours[idx1].sellingVolume+1e-7 >= vol1);
		assert(neighbours[idx2].sellingVolume+1e-7 >= vol2);
		neighbours[idx1].endowment-= vol1;		neighbours[idx2].acquired+= vol1;
		neighbours[idx2].endowment-= vol2;		neighbours[idx1].acquired+= vol2;
		neighbours[idx1].sellingVolume-= vol1;
		neighbours[idx2].sellingVolume-= vol2;
		if (neighbours[idx1].sellingVolume <0) neighbours[idx1].sellingVolume=0;
		if (neighbours[idx2].sellingVolume <0) neighbours[idx2].sellingVolume=0;
		if (neighbours[idx1].endowment <0) neighbours[idx1].endowment=0;
		if (neighbours[idx2].endowment <0) neighbours[idx2].endowment=0;
		}
	
	/** TODO: make private, or remove altogether */
	public double buyFor(double pay) {
		if (pay==0f) return 0f;
		if (pay>=totalCost()) return totalVolume();
		int i= 0;
		while (pay>costFn[i+1].pay) i++;	// safe from overruns
//		if (offers[i].rate()<=0) return costFn[i+1].get;	// TODO: wha??
		return costFn[i].get + (pay-costFn[i].pay)/offers[i+1].rate();
		}
	
	/** TODO: make private, or remove altogether */
	public double payFor(double get) {
		if (get>=totalVolume()) return totalCost();
		int i= 0;
		while (get>costFn[i+1].get) i++;	// assert(i<costFn.length);
		return costFn[i].pay + (get-costFn[i].get)*offers[i+1].rate();
		}
	
	/** prettyprint the array of deals given. Used for debugging. */
	private void show(String label, Deal[] deal) {
//		System.err.println(label);
		System.err.print(label+" / pay");
		for (int i=0; i<deal.length; i++)
			System.err.format("%6.2f",deal[i].pay);
		System.err.println();
		System.err.print("       \\ get");
		for (int i=0; i<deal.length; i++)
			System.err.format("%6.2f",deal[i].get);
		System.err.println();
		}
	
	public static void main(String[] args) {
		System.err.println("testing Market");
		int gameSize= 6;
		NodeState[] nodeStates= new NodeState[gameSize];
		for (int nsi=0; nsi<gameSize; nsi++) {
			nodeStates[nsi]= new NodeState(nsi,10.0f);
			}
		nodeStates[3].sellingPrice= 1;
		nodeStates[3].sellingVolume= 1;
		nodeStates[5].sellingPrice= 1.1f;
		nodeStates[5].sellingVolume= 2;
		nodeStates[2].sellingPrice= 1.1f;
		nodeStates[2].sellingVolume= 2;
		Market mkt= new Market(nodeStates, System.err);
		mkt.tieTest(1,false);
		mkt.tieTest(1,true);
		mkt.tieTest(2,false);
		mkt.tieTest(2,true);
		mkt.tieTest(3,false);
		mkt.tieTest(3,true);
		mkt.tieTest(4,false);
		mkt.tieTest(4,true);
		mkt.tieTest(5,false);
		mkt.tieTest(5,true);
		}
	
	} // EOC Market
